The present invention relates to efficient convolutions using polynomial covers and, more particularly, to an efficient method for pattern recognition and feature extraction using low degree polynomial covers for region approximation.
In pattern recognition, convolution is an important tool because of its translation invariance properties. Feature extraction is a typical example: the distance between a small pattern (i.e., the feature) is computed at all positions (i.e., translations) inside a large pattern (image). The resulting "distance image" is typically obtained by convolving the feature template with the larger pattern. There are many ways to perform this convolution. For example, a multiplication of the images (of the same size) in the Fourier domain corresponds to a convolution of the two images in the original domain. This Fourier method requires KN log N operations just to go in to and out of the Fourier domain (where N is the number of pixels in the image and K is a constant). Such a method is not appropriate for situations where the feature is small (e.g., 5.times.5 pixels) with respect to the image (e.g., 32.times.32 pixels).
In most feature extraction applications, the features are somewhat distorted in the original image (due to noise being present in the image) and the feature extraction process can be somewhat approximated without affecting the performance of the result. For example, the result of the convolution may be quantized or subjected to a threshold value to yield the presence and location of distinctive features. A complete discussion of this particular prior art feature extraction process may be found in an article entitled "Convolutional networks for images, speech, and time-series", by Y. LeCun et al., appearing in The Handbook of Brain Theory and Neural Networks, M. A. Arbib, ed. 1995. Indeed, it is often possible to quantize the signals before the convolution step with negligible degradation in performance.